package firstweek.four;

import java.util.Date;
import java.util.List;

/**
 * Created by zhour on 2016/8/4.
 */
public class QuickSort {
    public static void main(String[] args) {
        List<Salary> salaries = SortSalary.generateSalaryList();
        Salary[] salarieArray = salaries.toArray(new Salary[salaries.size()]);

        Date dateStart = new Date();
        quicksort(salarieArray, 0, salarieArray.length - 1);
        Date dateEnd = new Date();
        System.out.println("sort cost time : " + (dateEnd.getTime() - dateStart.getTime()) + "ms");
        System.out.println("max:" + (salarieArray[salarieArray.length - 1].baseSalary * 13 +
                salarieArray[salarieArray.length - 1].bonus));
        System.out.println("min:" + (salarieArray[0].baseSalary * 13 + salarieArray[0].bonus));
        for (int i = salarieArray.length - 1; i > salarieArray.length - 1 - 100; i--) {
            System.out.println(salarieArray[i].name + ":" + (salarieArray[i].baseSalary * 13 +
                    salarieArray[i].bonus)/10000+"万");
        }
    }

    /**
     * 最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。时间复杂度为O(n*n)

     在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlgn)

     尽管快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。
     * @param salaries
     * @param left
     * @param right
     */
    private static void quicksort(Salary[] salaries, int left, int right){
        if (left < right){
            Salary keySalary = salaries[left];
            int low = left;
            int high = right;
            while (low < high){
                while ((low < high) && (isBigger(salaries[high],keySalary))){
                    high--;
                }

                changePosition(salaries,low,high);
                while ((low < high) && (!isBigger(salaries[low],keySalary))){
                    low++;
                }
                changePosition(salaries,low,high);
            }
            salaries[low] = keySalary;
            quicksort(salaries, left,low-1);
            quicksort(salaries,low+1,right);
        }

    }

    private static boolean isBigger(Salary salary1, Salary salary2){
        return ((salary1.baseSalary*13+salary1.bonus) > (salary2.baseSalary*13+salary2.bonus));
    }

    private static void changePosition(Salary[] salaries, int position1, int position2){
        Salary tempSalary = salaries[position1];
        salaries[position1] = salaries[position2];
        salaries[position2] = tempSalary;
    }
}
